# -*-coding:utf-8-*-
__author__ = 'wss'

import random
import numpy as np

MAX_PATH = 1000  # 定义两个结点最远距离

# 定义简单图：以边为对象
class Graph():
    def __init__(self):
        self.edges = {}
        self.weights = {}
        # self.nodenum = nn
        # self.edgenum = self.get_edgenum()

    def neighbors(self, id):
        return self.edges[id]

    def get_nodenum(self):
        return len(self.edges.keys())

    def get_edgenum(self):
        num_sum = 0
        for key in self.edges.keys():
            num_sum += len(self.edges.get(key))
        return int(num_sum/2)

    def get_weight_matrix(self):
        node_list = list(self.edges.keys())  # 结点列表
        weight_matirx = np.array([[self.weights.get((node_list[i], node_list[j])) for i in range(len(node_list))] for j in range(len(node_list))])
        for i in range(len(node_list)):
            weight_matirx[i,i] = MAX_PATH
        return node_list, weight_matirx

    def get_weight_list(self):
        node_list = list(self.edges.keys())  # 结点列表
        weight_list = []
        for i in range(len(node_list)):
            for j in range(len(node_list)):
                if i < j:
                    weight_list.append([i, j, self.weights.get((node_list[i], node_list[j]))])
        return node_list, weight_list

# 定义网格图类
class SquredGrid(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.walls = []  # 障碍物

    def in_bounds(self, id):  # 图的边界
        (x, y) = id
        return 0 <= x < self.width and 0 <= y < self.height

    def passable(self, id):  # 判断是否是障碍物
        return id not in self.walls

    def neighbors(self, id):  # 四个方向
        (x, y) = id
        results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)]
        if (x + y) % 2 == 0:results.reverse()  # 为什么？
        results = filter(self.in_bounds, results)
        results = filter(self.passable, results)
        return results

# 加权图:集成网格图类
class GridWithWeights(SquredGrid):  # 继承无权图父类
    def __init__(self, width, height):
        super(GridWithWeights,self).__init__(width, height)
        self.weights = {}

    def cost(self, from_node, to_node):
        return self.weights.get(to_node, 1)  # 或的to_node对应的值，若不存在这返回1

# 定义网格图类
class SquredGrid_new(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.walls = []  # 障碍物

    def set_wall(self, bound_list):  # 根据边界点，将在边界点外的点视为障碍物
        for i in range(self.width):
            for j in range(self.height):
                id = (i,j)
                if not self.in_defbounds(id,bound_list):
                    self.walls.append(id)

    def in_bounds(self, id):  # 图的边界
        (x, y) = id
        return 0 <= x < self.width and 0 <= y < self.height

    def in_defbounds(self, id, bound_list=None):  # 用户自定义边界点
        def isPointIntersectsSegment(p,s,e):
            a = (s[0]-p[0],s[1]-p[1])
            b = (e[0]-p[0],e[1]-p[1])
            a_cross_b = a[0]*b[1]-b[0]*a[1]
            x_flag = min([s[0],e[0]])<=p[0]<=max([s[0],e[0]])
            y_flag = min([s[1],e[1]])<=p[1]<=max([s[1],e[1]])
            if (a_cross_b==0) and x_flag and y_flag:
                return True
            return False
        def isRayIntersectsSegment(p,s,e):
            # p为要判断点，s为线段起点，e为线段终点，均为(lon,lat)格式元组（经度,维度）
            if s[1] == e[1]:  # 排除线段与射线平行、重合，线段首尾端点重合的情况
                return False
            if (s[1]>p[1]) and (e[1]>p[1]):  # 线段是否在射线上边：线段两个点纵坐标都大于点的纵坐标
                return False
            if (s[1]<p[1]) and (e[1]<p[1]):  # 线段在射线下边：线段两个点的纵坐标都小于点的纵坐标
                return False
            if (s[1]==p[1]) and (e[1]>p[1]):  # 交点为上端点，对应s
                return False
            if (e[1]==p[1]) and (s[1]>p[1]):  # 交点为下端点，对应e
                return False
            if (s[0]<p[0]) and (e[1]<p[1]):  # 线段在射线左边
                return False
            xseg = e[0] - (e[0]-s[0])*(e[1]-p[1])/(e[1]-s[1])  # 求交
            if xseg<p[0]:
                return False
            return True
        # 输入：点、多边形三维数组
        if len(bound_list)==0:  # 如果没有自定义边界
            return self.in_bounds(id)
        p = id
        poly = bound_list
        sinsc = 0  # 交点个数
        for i in range(len(poly)-1):
            s = poly[i]
            e = poly[i+1]
            if isPointIntersectsSegment(p, s, e):
                return True
            if isRayIntersectsSegment(p, s, e):
                sinsc += 1
        # 判断首尾相连的边
        s = poly[len(poly)-1]
        e = poly[0]
        if isPointIntersectsSegment(p, s, e):
            return True
        if isRayIntersectsSegment(p, s, e):
            sinsc += 1
        return True if sinsc%2==1 else False

    def passable(self, id):  # 判断是否是障碍物
        return id not in self.walls

    def neighbors(self, id):  # 探索八个方向
        (x, y) = id
        results = [(x+1, y), (x+1,y-1), (x, y-1), (x-1,y-1), (x-1, y), (x-1,y+1), (x, y+1), (x+1,y+1)]
        if (x + y) % 2 == 0:results.reverse()  # 为什么？
        results = filter(self.in_bounds, results)  # 需改成自定义边界判断函数
        results = filter(self.passable, results)
        return results

    def neighbors_straight(self, id):  # 探索东南西北四个方向
        (x, y) = id
        results = [(x + 1, y), (x, y - 1), (x - 1, y), (x, y + 1)]
        if (x + y) % 2 == 0: results.reverse()  # 为什么？
        results = filter(self.in_bounds, results)  # 需改成自定义边界判断函数
        results = filter(self.passable, results)
        return results

    def neighbors_inclined(self, id):  # 探索东南、西南、东北、西北四个方向
        (x, y) = id
        results = [(x+1,y-1), (x-1,y-1), (x-1,y+1), (x+1,y+1)]
        if (x + y) % 2 == 0:results.reverse()  # 为什么？
        results = filter(self.in_bounds, results)# 需改成自定义边界判断函数
        results = filter(self.passable, results)
        return results

# 加权图:集成网格图类
class GridWithWeights_new(SquredGrid_new):  # 继承无权图父类
    def __init__(self, width, height):
        super(GridWithWeights_new,self).__init__(width, height)
        self.weights = {}

    def cost(self, from_node, to_node):
        return self.weights.get((from_node,to_node), 1)  # 或的to_node对应的值，若不存在这返回1

def main():
    # 定义10*10网格图，同时定义各方向权重
    diagram4 = GridWithWeights_new(10, 10)
    diagram4.walls = [(1, 7), (1, 8), (2, 7), (2, 8), (3, 7), (3, 8)]
    for idx_x in range(10):
        for idx_y in range(10):
            from_node = (idx_x, idx_y)
            if from_node not in diagram4.walls:  # 出发结点不能是障碍结点
                from_node_neighbors = diagram4.neighbors(from_node)  # 找到出发结点的邻居（肯定不是障碍结点或超范围结点）
                if len(from_node_neighbors) > 0:
                    for neighbor in from_node_neighbors:
                        val = random.randrange(10)
                        if not diagram4.weights.get((neighbor, from_node)):
                            if val == 9:
                                diagram4.weights[(from_node, neighbor)] = 50
                            else:
                                diagram4.weights[(from_node, neighbor)] = val
                        else:
                            diagram4.weights[(from_node, neighbor)] = diagram4.weights.get((neighbor, from_node))
                            # diagram4.weights = {loc: 5 for loc in [(3, 4), (3, 5), (4, 1), (4, 2),
                            #                                        (4, 3), (4, 4), (4, 5), (4, 6),
                            #                                        (4, 7), (4, 8), (5, 1), (5, 2),
                            #                                        (5, 3), (5, 4), (5, 5), (5, 6),
                            #                                        (5, 7), (5, 8), (6, 2), (6, 3),
                            #                                        (6, 4), (6, 5), (6, 6), (6, 7),
                            #                                        (7, 3), (7, 4), (7, 5)]}

if __name__ == '__main__':
    main()
